package 二叉树;

import java.util.HashMap;
import java.util.Map;

//106 中序后序遍历构造二叉树
public class Solution12 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        for (int i = 0 ; i < n ; i++) occ_map.put(inorder[i], i);
        return dfs(0, n - 1, 0, n - 1, inorder, postorder);
    }
    Map<Integer, Integer> occ_map = new HashMap<>();
    private TreeNode dfs(int in_lf, int in_rt, int ps_lf, int ps_rt, int[] inorder, int[] postorder) {
        if (in_lf > in_rt) return null;
        TreeNode node = new TreeNode(postorder[ps_rt]);
        int inorder_idx = occ_map.get(postorder[ps_rt]);
        int lf_cnt = inorder_idx - in_lf;
        node.left = dfs(in_lf, inorder_idx - 1, ps_lf, ps_lf + lf_cnt - 1, inorder, postorder);
        node.right = dfs(inorder_idx + 1, in_rt, ps_lf + lf_cnt, ps_rt - 1, inorder, postorder);
        return node;
    }
}
